package com.origin.niuke.dfs;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/9 11:54
 * 字符串的排列
 * 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列
 * 算法：深度优先搜索
 */
public class NC121 {
    public static void main(String[] args) {
        System.out.println(new NC121().Permutation("aab"));
    }

    ArrayList<String> ans = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if ("".equals(str)) return ans;
        char[] array = str.toCharArray();
        Arrays.sort(array);
        boolean[] visited = new boolean[str.length()];
        dfs(array, new StringBuilder(), visited);
        return ans;
    }
    void dfs(char[] array, StringBuilder sb, boolean[] visited) {
        if (sb.length() == array.length) {
            ans.add(sb.toString());
            return;
        }
        for (int i = 0; i < array.length; i++) {
            if (visited[i]) continue;
            if (i != 0 && array[i] == array[i - 1] && !visited[i - 1]) continue;
            sb.append(array[i]);
            visited[i] = true;
            dfs(array, sb, visited);
            visited[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }

}
